class Solution {
public:
    //去除所有空格并在相邻单词之间添加空格, 双指针
    void removeExtraSpaces(string& s) {  // 参考27.移除元素 思想
        int left = 0;
        for(int right = 0; right < s.size(); ++right){
            if(s[right] != ' '){
                if(left != 0 ) s[left++] = ' ';   // 为单词间添加空格
                while(right < s.size() && s[right] != ' ')
                    s[left++] = s[right++];   // 填充单词
            }
        }
        s.resize(left);
    }
    // 双指针范围反转字符串
    void reverseStr(string& s, int l, int r){
        for(int i = l,j = r; i < j; ++i, --j)
            swap(s[i], s[j]);
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverseStr(s, 0, s.size()-1);
        int start = 0;
        for(int i = 0; i <= s.size(); ++i){  // 因为取 i- 1
            if(s[i] == ' ' || i == s.size()){  //到达空格或串尾
                reverseStr(s, start, i-1);   // 反转单词
                start = i + 1;  // 下一个单词
            }
        }
        return s;
    }
};